//给定一个长度为 n 的链表 head 
//
// 对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。 
//
// 返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点
//，设置 answer[i] = 0 。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：head = [2,1,5]
//输出：[5,5,0]
// 
//
// 示例 2： 
//
// 
//
// 
//输入：head = [2,7,4,3,5]
//输出：[7,0,5,5,0]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点数为 n 
// 1 <= n <= 10⁴ 
// 1 <= Node.val <= 10⁹ 
// 
//
// Related Topics 栈 数组 链表 单调栈 👍 331 👎 0


package leetcode.editor.cn;

import leetcode.editor.cn.helper.ListNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

class NextGreaterNodeInLinkedList {
    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode listNode = new ListNode(-1), p = listNode;
        for (int val : Arrays.asList(2, 7, 4, 3, 5)) {
            p.next = new ListNode(val);
            p = p.next;
        }
        int[] res = solution.nextLargerNodes(listNode.next);
        System.out.println(Arrays.toString(res));
    }

    static
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
    class Solution {
        public int[] nextLargerNodes(ListNode head) {
            ArrayList<Integer> list = new ArrayList<>();
            while (head != null) {
                list.add(head.val);
                head = head.next;
            }
            int n = list.size();
            int[] ans = new int[n];
            Deque<Integer> stack = new LinkedList<>();
            for (int i = 0; i < n; i++) {
                while (!stack.isEmpty() && list.get(stack.getLast()) < list.get(i)){
                    Integer idx = stack.removeLast();
                    ans[idx] = list.get(i);
                }
                stack.addLast(i);
            }
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}